<!DOCTYPE html>












  


<html class="theme-next gemini use-motion" lang="zh-CN">
<head><meta name="generator" content="Hexo 3.8.0">
  <meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
























<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2">

<link rel="stylesheet" href="/css/main.css?v=7.0.1">


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=7.0.1">


  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=7.0.1">


  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=7.0.1">


  <link rel="mask-icon" href="/images/logo.svg?v=7.0.1" color="#222">







<script id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '7.0.1',
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false,"dimmer":false},
    back2top: true,
    back2top_sidebar: true,
    fancybox: false,
    fastclick: false,
    lazyload: false,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>


  




  <meta name="description" content="你若对得起时间，时间便对得起你">
<meta property="og:type" content="website">
<meta property="og:title" content="yukong&#39;s blog">
<meta property="og:url" content="http://www.yukonga.cn/index.html">
<meta property="og:site_name" content="yukong&#39;s blog">
<meta property="og:description" content="你若对得起时间，时间便对得起你">
<meta property="og:locale" content="zh-CN">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="yukong&#39;s blog">
<meta name="twitter:description" content="你若对得起时间，时间便对得起你">



  <link rel="alternate" href="/atom.xml" title="yukong's blog" type="application/atom+xml">




  <link rel="canonical" href="http://www.yukonga.cn/">



<script id="page.configurations">
  CONFIG.page = {
    sidebar: "",
  };
</script>

  <title>yukong's blog</title>
  






  <script>
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?45b7a3cfe46b3fa2c5d46f59f590664e";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>







  <noscript>
  <style>
  .use-motion .motion-element,
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-title { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope="" itemtype="http://schema.org/WebPage" lang="zh-CN">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope="" itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta">
    

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">yukong's blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
    
      
        <p class="site-subtitle">learning program</p>
      
    
    
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>



<nav class="site-nav">
  
    <ul id="menu" class="menu">
      
        
        
        
          
          <li class="menu-item menu-item-home menu-item-active">

    
    
    
      
    

    

    <a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-about">

    
    
    
      
    

    

    <a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-user"></i> <br>关于</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-tags">

    
    
    
      
    

    

    <a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-categories">

    
    
    
      
    

    

    <a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>

  </li>
        
        
        
          
          <li class="menu-item menu-item-archives">

    
    
    
      
    

    

    <a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>

  </li>

      
      
    </ul>
  

  

  
</nav>



  



</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          
            

          
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2020/03/30/230-Kth-Smallest-Element-in-a-BST/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2020/03/30/230-Kth-Smallest-Element-in-a-BST/" class="post-title-link" itemprop="url">230. Kth Smallest Element in a BST</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2020-03-30 11:44:20 / 修改时间：11:47:21" itemprop="dateCreated datePublished" datetime="2020-03-30T11:44:20+08:00">2020-03-30</time>
            

            
              

              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2020/03/30/230-Kth-Smallest-Element-in-a-BST/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2020/03/30/230-Kth-Smallest-Element-in-a-BST/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2020/03/30/230-Kth-Smallest-Element-in-a-BST/" class="leancloud_visitors" data-flag-title="230. Kth Smallest Element in a BST">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <h2 id="230-kth-smallest-element-in-a-bst"><a class="markdownIt-Anchor" href="#230-kth-smallest-element-in-a-bst"></a> 230. Kth Smallest Element in a BST</h2>
<blockquote>
<p>原题地址 <a href="https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst/" target="_blank" rel="noopener">230. Kth Smallest Element in a BST</a></p>
</blockquote>
<h2 id="解题思路"><a class="markdownIt-Anchor" href="#解题思路"></a> 解题思路</h2>
<p>由于给的二叉搜索树，总所周知二叉搜索树的中序遍历是有序的。所以这题可以变相的理解的为有序数组的中的第k个数</p>
<p>二叉树的中路遍历有两种方法, 递归、非递归(借助 栈).</p>
<p>我们先看递归</p>
<h3 id="递归解法-1"><a class="markdownIt-Anchor" href="#递归解法-1"></a> 递归解法-1</h3>
<p>我们通过中序遍历,把遍历的值存在<code>List&lt;Integer&gt; res</code> 中, 然后返回<code>res.get(k -1)</code> 即,.很容易写出如下代码.</p>
<h4 id="ac代码"><a class="markdownIt-Anchor" href="#ac代码"></a> AC代码</h4>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">kthSmallest</span><span class="params">(TreeNode root, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    ArrayList&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    inorder(root, res);</span><br><span class="line">    <span class="keyword">return</span> res.get(k - <span class="number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> ArrayList&lt;Integer&gt; <span class="title">inorder</span><span class="params">(TreeNode root, ArrayList&lt;Integer&gt; res)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (root == <span class="keyword">null</span>) &#123;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">    inorder(root.left, res);</span><br><span class="line">    res.add(root.val);</span><br><span class="line">    inorder(root.right, res);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>很明显时间复杂是O(n),空间复杂度是O(n).</p>
<h3 id="递归解法-2"><a class="markdownIt-Anchor" href="#递归解法-2"></a> 递归解法-2</h3>
<p>其实我们没用必要记录每个节点的值, 我们只需要遍历到第k个节点, 并且记录它的值即可,虽然这样不能避免递归的次数,但是可以空间复杂度到O(1).</p>
<h4 id="ac代码-2"><a class="markdownIt-Anchor" href="#ac代码-2"></a> AC代码</h4>
<p>很容易写出如下代码.</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> num = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">private</span> <span class="keyword">int</span> count = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">kthSmallest</span><span class="params">(TreeNode root, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    inorder(root, k);</span><br><span class="line">    <span class="keyword">return</span> num;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">private</span> <span class="keyword">void</span> <span class="title">inorder</span><span class="params">(TreeNode root, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    <span class="comment">// 减枝</span></span><br><span class="line">    <span class="keyword">if</span> (root == <span class="keyword">null</span> || count &gt;= k) &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    inorder(root.left, k);</span><br><span class="line">    count++;</span><br><span class="line">    <span class="keyword">if</span> (k == count) &#123;</span><br><span class="line">        num = root.val;</span><br><span class="line">    &#125;</span><br><span class="line">    inorder(root.right, k);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>时间复杂是O(n),空间复杂度是O(1).</p>
<h3 id="非递归解法栈"><a class="markdownIt-Anchor" href="#非递归解法栈"></a> 非递归解法(栈)</h3>
<p>总所周知通过栈我们能实现二叉树的中序遍历, 非递归的遍历的好处就是我们能提前结束,而不需等到整个二叉树遍历完.</p>
<p>同时在遍历的时候取第k个数的值即可.</p>
<h4 id="ac代码-3"><a class="markdownIt-Anchor" href="#ac代码-3"></a> AC代码</h4>
<p>代码如下</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">kthSmallest</span><span class="params">(TreeNode root, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">    Stack&lt;TreeNode&gt; stack = <span class="keyword">new</span> Stack&lt;&gt;();</span><br><span class="line">    <span class="keyword">while</span> (<span class="keyword">true</span>) &#123;</span><br><span class="line">        <span class="keyword">while</span> (root != <span class="keyword">null</span>) &#123;</span><br><span class="line">            stack.push(root);</span><br><span class="line">            root = root.left;</span><br><span class="line">        &#125;</span><br><span class="line">        root = stack.pop();</span><br><span class="line">        <span class="keyword">if</span> (--k == <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> root.val;</span><br><span class="line">        &#125;</span><br><span class="line">        root = root.right;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
          
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2019/05/28/LeetCode-951-Flip-Equivalent-Binary-Trees/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2019/05/28/LeetCode-951-Flip-Equivalent-Binary-Trees/" class="post-title-link" itemprop="url">LeetCode-951. Flip Equivalent Binary Trees</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-05-28 14:19:41 / 修改时间：14:29:32" itemprop="dateCreated datePublished" datetime="2019-05-28T14:19:41+08:00">2019-05-28</time>
            

            
              

              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2019/05/28/LeetCode-951-Flip-Equivalent-Binary-Trees/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2019/05/28/LeetCode-951-Flip-Equivalent-Binary-Trees/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2019/05/28/LeetCode-951-Flip-Equivalent-Binary-Trees/" class="leancloud_visitors" data-flag-title="LeetCode-951. Flip Equivalent Binary Trees">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p><a href="https://leetcode-cn.com/problems/flip-equivalent-binary-trees/" target="_blank" rel="noopener">原题链接</a></p>
<h2 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h2>
<p>我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。</p>
<p>只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X <em>翻转等价</em>于二叉树 Y。</p>
<p>编写一个判断两个二叉树是否是<em>翻转等价</em>的函数。这些树由根节点 <code>root1</code> 和 <code>root2</code> 给出。</p>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2019/05/28/LeetCode-951-Flip-Equivalent-Binary-Trees/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2019/05/27/LeetCode-338-Counting-Bits/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2019/05/27/LeetCode-338-Counting-Bits/" class="post-title-link" itemprop="url">LeetCode-338 Counting Bits</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-05-27 15:27:15 / 修改时间：15:42:16" itemprop="dateCreated datePublished" datetime="2019-05-27T15:27:15+08:00">2019-05-27</time>
            

            
              

              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2019/05/27/LeetCode-338-Counting-Bits/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2019/05/27/LeetCode-338-Counting-Bits/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2019/05/27/LeetCode-338-Counting-Bits/" class="leancloud_visitors" data-flag-title="LeetCode-338 Counting Bits">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          
            <p><a href="https://leetcode-cn.com/problems/counting-bits/submissions/" target="_blank" rel="noopener">原题链接</a></p>
<h2 id="题目描述"><a class="markdownIt-Anchor" href="#题目描述"></a> 题目描述</h2>
<p>给定一个非负整数 <strong>num</strong>。对于 <strong>0 ≤ i ≤ num</strong> 范围中的每个数字 <strong>i</strong> ，计算其二进制数中的 1 的数目并将它们作为数组返回。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight angelscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: <span class="number">2</span></span><br><span class="line">输出: [<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>]</span><br></pre></td></tr></table></figure>
<p><strong>示例 2:</strong></p>
<figure class="highlight angelscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入: <span class="number">5</span></span><br><span class="line">输出: [<span class="number">0</span>,<span class="number">1</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">1</span>,<span class="number">2</span>]</span><br></pre></td></tr></table></figure>
<p><strong>进阶:</strong></p>
<ul>
<li>给出时间复杂度为**O(n*sizeof(integer))<strong>的解答非常容易。但你可以在线性时间</strong>O(n)**内用一趟扫描做到吗？</li>
<li>要求算法的空间复杂度为<strong>O(n)</strong>。</li>
<li>你能进一步完善解法吗？要求在C<ins>或任何其他语言中不使用任何内置函数（如 C</ins> 中的 <strong>__builtin_popcount</strong>）来执行此操作。</li>
</ul>
<h2 id="解题思路"><a class="markdownIt-Anchor" href="#解题思路"></a> 解题思路</h2>
<p><code>i &amp; (i - 1)</code>去掉<code>i</code>最右边的一个1；因<code>i &amp; (i - 1）&lt; i</code>，故<code>result[i &amp; (i - 1)]</code>已计算，所以<code>i</code>中1的个数为<code>result[i &amp; (i - 1)] + 1</code></p>
<h2 id="ac代码"><a class="markdownIt-Anchor" href="#ac代码"></a> AC代码</h2>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="keyword">int</span>[] countBits(<span class="keyword">int</span> num) &#123;</span><br><span class="line"> </span><br><span class="line">    <span class="keyword">int</span>[] res = <span class="keyword">new</span> <span class="keyword">int</span>[num + <span class="number">1</span>];</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= num ; i++) &#123;</span><br><span class="line">        res[i] = res[i &amp; (i - <span class="number">1</span>)] + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

          
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2019/04/12/【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2019/04/12/【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读/" class="post-title-link" itemprop="url">【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-04-12 15:58:25" itemprop="dateCreated datePublished" datetime="2019-04-12T15:58:25+08:00">2019-04-12</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-07-27 14:07:47" itemprop="dateModified" datetime="2019-07-27T14:07:47+08:00">2019-07-27</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/SpringSecurity/" itemprop="url" rel="index"><span itemprop="name">SpringSecurity</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2019/04/12/【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2019/04/12/【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2019/04/12/【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读/" class="leancloud_visitors" data-flag-title="【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <h2 id="概要"><a class="markdownIt-Anchor" href="#概要"></a> 概要</h2>
<p>前面一节，通过简单配置即可实现SpringSecurity表单认证功能，而今天这一节将通过阅读源码的形式来学习SpringSecurity是如何实现这些功能, 前方高能预警，<strong><code>本篇分析源码篇幅较长</code></strong>。</p>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2019/04/12/【SpringSecurity系列02】SpringSecurity UsernamePasswordAuthenticationFilter认证逻辑源码解读/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2019/04/11/【SpringSecurity系列01】初识SpringSecurity/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2019/04/11/【SpringSecurity系列01】初识SpringSecurity/" class="post-title-link" itemprop="url">【SpringSecurity系列01】初识SpringSecurity</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-04-11 16:20:09" itemprop="dateCreated datePublished" datetime="2019-04-11T16:20:09+08:00">2019-04-11</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-05-24 17:27:17" itemprop="dateModified" datetime="2019-05-24T17:27:17+08:00">2019-05-24</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/SpringSecurity/" itemprop="url" rel="index"><span itemprop="name">SpringSecurity</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2019/04/11/【SpringSecurity系列01】初识SpringSecurity/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2019/04/11/【SpringSecurity系列01】初识SpringSecurity/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2019/04/11/【SpringSecurity系列01】初识SpringSecurity/" class="leancloud_visitors" data-flag-title="【SpringSecurity系列01】初识SpringSecurity">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>​    什么是<code>SpringSecurity</code> ？</p>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2019/04/11/【SpringSecurity系列01】初识SpringSecurity/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2019/01/18/56-合并区间-Merge-Intervals/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2019/01/18/56-合并区间-Merge-Intervals/" class="post-title-link" itemprop="url">56. 合并区间(Merge Intervals)</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-01-18 16:37:47 / 修改时间：16:41:21" itemprop="dateCreated datePublished" datetime="2019-01-18T16:37:47+08:00">2019-01-18</time>
            

            
              

              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2019/01/18/56-合并区间-Merge-Intervals/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2019/01/18/56-合并区间-Merge-Intervals/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2019/01/18/56-合并区间-Merge-Intervals/" class="leancloud_visitors" data-flag-title="56. 合并区间(Merge Intervals)">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>给出一个区间的集合，请合并所有重叠的区间。</p>
<p><strong>示例 1:</strong></p>
<figure class="highlight angelscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入: [[<span class="number">1</span>,<span class="number">3</span>],[<span class="number">2</span>,<span class="number">6</span>],[<span class="number">8</span>,<span class="number">10</span>],[<span class="number">15</span>,<span class="number">18</span>]]</span><br><span class="line">输出: [[<span class="number">1</span>,<span class="number">6</span>],[<span class="number">8</span>,<span class="number">10</span>],[<span class="number">15</span>,<span class="number">18</span>]]</span><br><span class="line">解释: 区间 [<span class="number">1</span>,<span class="number">3</span>] 和 [<span class="number">2</span>,<span class="number">6</span>] 重叠, 将它们合并为 [<span class="number">1</span>,<span class="number">6</span>].</span><br></pre></td></tr></table></figure>
<p><strong>示例 2:</strong></p>
<figure class="highlight angelscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">输入: [[<span class="number">1</span>,<span class="number">4</span>],[<span class="number">4</span>,<span class="number">5</span>]]</span><br><span class="line">输出: [[<span class="number">1</span>,<span class="number">5</span>]]</span><br><span class="line">解释: 区间 [<span class="number">1</span>,<span class="number">4</span>] 和 [<span class="number">4</span>,<span class="number">5</span>] 可被视为重叠区间。</span><br></pre></td></tr></table></figure>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2019/01/18/56-合并区间-Merge-Intervals/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2019/01/17/780-到达终点-Reaching-Points/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2019/01/17/780-到达终点-Reaching-Points/" class="post-title-link" itemprop="url"> 780. 到达终点 (Reaching Points)</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2019-01-17 17:10:17" itemprop="dateCreated datePublished" datetime="2019-01-17T17:10:17+08:00">2019-01-17</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-01-18 16:38:55" itemprop="dateModified" datetime="2019-01-18T16:38:55+08:00">2019-01-18</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2019/01/17/780-到达终点-Reaching-Points/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2019/01/17/780-到达终点-Reaching-Points/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2019/01/17/780-到达终点-Reaching-Points/" class="leancloud_visitors" data-flag-title=" 780. 到达终点 (Reaching Points)">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>从点 <code>(x, y)</code> 可以<strong>转换</strong>到 <code>(x, x+y)</code>  或者 <code>(x+y, y)</code>。</p>
<p>给定一个起点 <code>(sx, sy)</code> 和一个终点 <code>(tx, ty)</code>，如果通过一系列的<strong>转换</strong>可以从起点到达终点，则返回 <code>True</code>，否则返回 <code>False</code>。</p>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2019/01/17/780-到达终点-Reaching-Points/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2018/11/29/基于SpringCloud-Finchley-SR1-、SpringBoot-2-x、-vue、element-ui-微服务基础脚手架/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2018/11/29/基于SpringCloud-Finchley-SR1-、SpringBoot-2-x、-vue、element-ui-微服务基础脚手架/" class="post-title-link" itemprop="url">基于SpringCloud Finchley.SR1 、SpringBoot 2.x、 vue、element-ui 微服务基础脚手架</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2018-11-29 15:48:17" itemprop="dateCreated datePublished" datetime="2018-11-29T15:48:17+08:00">2018-11-29</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-05-07 14:29:20" itemprop="dateModified" datetime="2019-05-07T14:29:20+08:00">2019-05-07</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/SpringCloud/" itemprop="url" rel="index"><span itemprop="name">SpringCloud</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2018/11/29/基于SpringCloud-Finchley-SR1-、SpringBoot-2-x、-vue、element-ui-微服务基础脚手架/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2018/11/29/基于SpringCloud-Finchley-SR1-、SpringBoot-2-x、-vue、element-ui-微服务基础脚手架/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2018/11/29/基于SpringCloud-Finchley-SR1-、SpringBoot-2-x、-vue、element-ui-微服务基础脚手架/" class="leancloud_visitors" data-flag-title="基于SpringCloud Finchley.SR1 、SpringBoot 2.x、 vue、element-ui 微服务基础脚手架">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>panda是基于SpringCloud Finchley.SR1 、SpringBoot 2.x、 vue、element-ui 微服务基础脚手架<br>
对于日常开发而言提供基础权限控制，动态菜单，才用前后端分离架构，前台采用vue 后台使用springcloud提供rest接口。对于以后开发，只需要在1panda-service` 添加业务模块即可，大大减少工作量。</p>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2018/11/29/基于SpringCloud-Finchley-SR1-、SpringBoot-2-x、-vue、element-ui-微服务基础脚手架/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2018/09/10/【java并发编程实战6】AQS之独占锁ReentrantLock实现/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2018/09/10/【java并发编程实战6】AQS之独占锁ReentrantLock实现/" class="post-title-link" itemprop="url">【java并发编程实战6】AQS之独占锁ReentrantLock实现</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2018-09-10 18:11:08" itemprop="dateCreated datePublished" datetime="2018-09-10T18:11:08+08:00">2018-09-10</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-05-07 13:59:11" itemprop="dateModified" datetime="2019-05-07T13:59:11+08:00">2019-05-07</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/java并发编程实战/" itemprop="url" rel="index"><span itemprop="name">java并发编程实战</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2018/09/10/【java并发编程实战6】AQS之独占锁ReentrantLock实现/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2018/09/10/【java并发编程实战6】AQS之独占锁ReentrantLock实现/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2018/09/10/【java并发编程实战6】AQS之独占锁ReentrantLock实现/" class="leancloud_visitors" data-flag-title="【java并发编程实战6】AQS之独占锁ReentrantLock实现">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <h1 id="前言"><a class="markdownIt-Anchor" href="#前言"></a> 前言</h1>
<p>自从JDK1.5后，jdk新增一个并发工具包<code>java.util.concurrent</code>，提供了一系列的并发工具类。而今天我们需要学习的是<code>java.util.concurrent.lock</code>也就是它下面的lock包，其中有一个最为常见类<code>ReentrantLock</code>，</p>
<p>我们知道<code>ReentrantLock</code>的功能是实现代码段的并发访问控制，也就是通常意义上所说的锁。之前我们也学习过一种锁的实现，也就是<code>synchronized</code>关键词，<code>synchronized</code>是在字节码层面，通过对象的监视器锁实现的。那么<code>ReentrantLock</code>又是怎么实现的呢？</p>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2018/09/10/【java并发编程实战6】AQS之独占锁ReentrantLock实现/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  

  <article class="post post-type-normal" itemscope="" itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://www.yukonga.cn/2018/09/07/【java并发编程实战5】线程与线程通信/">

    <span hidden itemprop="author" itemscope="" itemtype="http://schema.org/Person">
      <meta itemprop="name" content="yukong">
      <meta itemprop="description" content="你若对得起时间，时间便对得起你">
      <meta itemprop="image" content="/uploads/avatar.png">
    </span>

    <span hidden itemprop="publisher" itemscope="" itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="yukong's blog">
    </span>

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
                
                
                <a href="/2018/09/07/【java并发编程实战5】线程与线程通信/" class="post-title-link" itemprop="url">【java并发编程实战5】线程与线程通信</a>
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">

            
            
            

            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              

              
                
              

              <time title="创建时间：2018-09-07 17:36:13" itemprop="dateCreated datePublished" datetime="2018-09-07T17:36:13+08:00">2018-09-07</time>
            

            
              

              
                
                <span class="post-meta-divider">|</span>
                

                <span class="post-meta-item-icon">
                  <i class="fa fa-calendar-check-o"></i>
                </span>
                
                  <span class="post-meta-item-text">更新于</span>
                
                <time title="修改时间：2019-05-07 13:59:08" itemprop="dateModified" datetime="2019-05-07T13:59:08+08:00">2019-05-07</time>
              
            
          </span>

          
            <span class="post-category">
            
              <span class="post-meta-divider">|</span>
            
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              
                <span class="post-meta-item-text">分类于</span>
              
              
                <span itemprop="about" itemscope="" itemtype="http://schema.org/Thing"><a href="/categories/java并发编程实战/" itemprop="url" rel="index"><span itemprop="name">java并发编程实战</span></a></span>

                
                
              
            </span>
          

          
            
            
              
              <span class="post-comments-count">
                <span class="post-meta-divider">|</span>
                <span class="post-meta-item-icon">
                  <i class="fa fa-comment-o"></i>
                </span>
            
                <span class="post-meta-item-text">评论数：</span>
                <a href="/2018/09/07/【java并发编程实战5】线程与线程通信/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count valine-comment-count" data-xid="/2018/09/07/【java并发编程实战5】线程与线程通信/" itemprop="commentCount"></span>
                </a>
              </span>
            
          

          
          
            <span id="/2018/09/07/【java并发编程实战5】线程与线程通信/" class="leancloud_visitors" data-flag-title="【java并发编程实战5】线程与线程通信">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-eye"></i>
              </span>
              
                <span class="post-meta-item-text">阅读次数：</span>
              
                <span class="leancloud-visitors-count"></span>
            </span>
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body" itemprop="articleBody">

      
      

      
        
          <p>现代操作系统在运行一个程序，会为其创建一个进程。然后它调度的最小单元是线程，线程也叫轻量级进程(Light Weight Process)，在一个进程中可以创建多个线程，这些线程都有各自的计算器，堆，栈和局部变量</p>
          <!--noindex-->
          
            <div class="post-button text-center">
              <a class="btn" href="/2018/09/07/【java并发编程实战5】线程与线程通信/#more" rel="contents">
                阅读全文 &raquo;
              </a>
            </div>
          
          <!--/noindex-->
        
      
    </div>

    

    
    
    

    

    
      
    
    

    
    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="page-number" href="/page/3/">3</a><a class="extend next" rel="next" href="/page/2/"><i class="fa fa-angle-right" aria-label="下一页"></i></a>
  </nav>



          </div>
          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      

      <div class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope="" itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image" src="/uploads/avatar.png" alt="yukong">
            
              <p class="site-author-name" itemprop="name">yukong</p>
              <div class="site-description motion-element" itemprop="description">你若对得起时间，时间便对得起你</div>
          </div>

          
            <nav class="site-state motion-element">
              
                <div class="site-state-item site-state-posts">
                
                  <a href="/archives/">
                
                    <span class="site-state-item-count">26</span>
                    <span class="site-state-item-name">日志</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-categories">
                  
                    
                      <a href="/categories/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">6</span>
                    <span class="site-state-item-name">分类</span>
                  </a>
                </div>
              

              
                
                
                <div class="site-state-item site-state-tags">
                  
                    
                      <a href="/tags/">
                    
                  
                    
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                      
                    
                    <span class="site-state-item-count">36</span>
                    <span class="site-state-item-name">标签</span>
                  </a>
                </div>
              
            </nav>
          

          
            <div class="feed-link motion-element">
              <a href="/atom.xml" rel="alternate">
                <i class="fa fa-rss"></i>
                RSS
              </a>
            </div>
          

          

          
            <div class="links-of-author motion-element">
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="https://github.com/YuKongEr" title="GitHub &rarr; https://github.com/YuKongEr" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="mailto:yukongcode@gmail.com" title="E-Mail &rarr; mailto:yukongcode@gmail.com" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                </span>
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="https://www.jianshu.com/u/bc2e35b66293" title="简书 &rarr; https://www.jianshu.com/u/bc2e35b66293" rel="noopener" target="_blank"><i class="fa fa-fw fa-skype"></i>简书</a>
                </span>
              
                <span class="links-of-author-item">
                  
                  
                    
                  
                  
                    
                  
                  <a href="https://blog.csdn.net/xp541130126" title="csdn &rarr; https://blog.csdn.net/xp541130126" rel="noopener" target="_blank"><i class="fa fa-fw fa-vk"></i>csdn</a>
                </span>
              
            </div>
          

          

          
          

          
            
          
          

        </div>
      </div>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>
  


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love" id="animate">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">yukong</span>

  

  
</div>
<div class="BbeiAn-info">
浙ICP备 -
<a target="_blank" href="http://www.miitbeian.gov.cn">19015067号</a>

</div>









        
<div class="busuanzi-count">
  <script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>

  
    <span class="post-meta-item-icon">
      <i class="fa fa-user"></i>
      您是访问本站的第&nbsp
    </span>
    <span class="site-uv" title="总访客量">
      <span class="busuanzi-value" id="busuanzi_value_site_uv"></span>
      &nbsp 位朋友
    </span>
  

  
    <span class="post-meta-divider">|</span>
  

  
    <span class="post-meta-item-icon">
      <i class="fa fa-eye"></i>
      本站总共访问&nbsp
    </span>
    <span class="site-pv" title="总访问量">
      <span class="busuanzi-value" id="busuanzi_value_site_pv"></span>
      次
    </span>
  
</div>









        
      </div>
    </footer>

    

    

    

    
  </div>

  

<script>
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>


























  
  <script src="/lib/jquery/index.js?v=2.1.3"></script>

  
  <script src="/lib/velocity/velocity.min.js?v=1.2.1"></script>

  
  <script src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>


  


  <script src="/js/src/utils.js?v=7.0.1"></script>

  <script src="/js/src/motion.js?v=7.0.1"></script>



  
  


  <script src="/js/src/affix.js?v=7.0.1"></script>

  <script src="/js/src/schemes/pisces.js?v=7.0.1"></script>




  

  


  <script src="/js/src/next-boot.js?v=7.0.1"></script>


  

  

  

  
  

<script src="//cdn1.lncld.net/static/js/3.11.1/av-min.js"></script>



<script src="//unpkg.com/valine/dist/Valine.min.js"></script>

<script>
  var GUEST = ['nick', 'mail', 'link'];
  var guest = 'nick,mail,link';
  guest = guest.split(',').filter(function(item) {
    return GUEST.indexOf(item) > -1;
  });
  new Valine({
    el: '#comments',
    verify: false,
    notify: false,
    appId: 'UXuVTqzKQgCJRWTkO8K60EXL-gzGzoHsz',
    appKey: 'n3ohmj1CGAM1GUfp6SqF4LXh',
    placeholder: 'Just go go',
    avatar: 'mm',
    meta: guest,
    pageSize: '10' || 10,
    visitor: false,
    lang: 'zh-cn' || 'zh-cn'
  });
</script>





  




  
  
  <script>
    
    function showTime(Counter) {
      var entries = [];
      var $visitors = $('.leancloud_visitors');

      $visitors.each(function() {
        entries.push( $(this).attr('id').trim() );
      });

      Counter('get', '/classes/Counter', { where: JSON.stringify({ url: { '$in': entries } }) })
        .done(function({ results }) {
          var COUNT_CONTAINER_REF = '.leancloud-visitors-count';

          if (results.length === 0) {
            $visitors.find(COUNT_CONTAINER_REF).text(0);
            return;
          }

          for (var i = 0; i < results.length; i++) {
            var item = results[i];
            var url = item.url;
            var time = item.time;
            var element = document.getElementById(url);

            $(element).find(COUNT_CONTAINER_REF).text(time);
          }
          for (var i = 0; i < entries.length; i++) {
            var url = entries[i];
            var element = document.getElementById(url);
            var countSpan = $(element).find(COUNT_CONTAINER_REF);
            if (countSpan.text() == '') {
              countSpan.text(0);
            }
          }
        })
        .fail(function ({ responseJSON }) {
          console.log('LeanCloud Counter Error: ' + responseJSON.code + ' ' + responseJSON.error);
        });
    }
    

    $(function() {
      $.get('https://app-router.leancloud.cn/2/route?appId=' + 'UXuVTqzKQgCJRWTkO8K60EXL-gzGzoHsz')
        .done(function({ api_server }) {
          var Counter = function(method, url, data) {
            return $.ajax({
              method: method,
              url: 'https://' + api_server + '/1.1' + url,
              headers: {
                'X-LC-Id': 'UXuVTqzKQgCJRWTkO8K60EXL-gzGzoHsz',
                'X-LC-Key': 'n3ohmj1CGAM1GUfp6SqF4LXh',
                'Content-Type': 'application/json',
              },
              data: data
            });
          };
          
            if ($('.post-title-link').length >= 1) {
              showTime(Counter);
            }
          
        });
    });
  </script>



  

  

  

  

  

  

  

  

  

  

  
<script>
  $('.highlight').each(function(i, e) {
    var $wrap = $('<div>').addClass('highlight-wrap');
    $(e).after($wrap);
    $wrap.append($('<button>').addClass('copy-btn').append('复制').on('click', function(e) {
      var code = $(this).parent().find('.code').find('.line').map(function(i, e) {
        return $(e).text();
      }).toArray().join('\n');
      var ta = document.createElement('textarea');
      var yPosition = window.pageYOffset || document.documentElement.scrollTop;
      ta.style.top = yPosition + 'px'; // Prevent page scroll
      ta.style.position = 'absolute';
      ta.style.opacity = '0';
      ta.readOnly = true;
      ta.value = code;
      document.body.appendChild(ta);
      ta.select();
      ta.setSelectionRange(0, code.length);
      ta.readOnly = false;
      var result = document.execCommand('copy');
      
        if (result) $(this).text('复制成功');
        else $(this).text('复制失败');
      
      ta.blur(); // For iOS
      $(this).blur();
    })).on('mouseleave', function(e) {
      var $b = $(this).find('.copy-btn');
      setTimeout(function() {
        $b.text('复制');
      }, 300);
    }).append(e);
  })
</script>


  

  

</body>
</html>
